/* 442. 数组中重复的数据 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */

/* 排序 */
var findDuplicates = function (nums) {
    const n = nums.length
    const result = []
    if (n === 1) return result
    nums.sort((a, b) => a - b)
    for (let i = 0; i < n; i++) {
        const cur = nums[i], next = nums[i + 1]
        if (cur === next) {
            result.push(cur)
        }
    }
    return result
};
/* 
    将元素交换到对应的位置 
    给定的n个数都在[1,n] 如果有数字出现了两次就意味着 [1,n] 中有数字没有出现过
    因此我们可以尝试将每一个数放在对应的位置，由于数组的下标范围是[0,n-1] 我们需要将
    i 放在数组下标尾 i- 1的位置    
*/
var findDuplicates = function (nums) {
    const swap = (nums, index1, index2) => {
        const temp = nums[index1]
        nums[index1] = nums[index2]
        nums[index2] = temp
    }
    const n = nums.length
    for (let i = 0; i < n; i++) {
        while (nums[i] !== nums[nums[i] - 1]) {
            swap(nums, i, nums[i] - 1)
        }
    }
    const ans = []
    for (let i = 0; i < n; i++) {
        if (nums[i] - 1 !== i) {
            ans.push(nums[i])
        }
    }
}
/* 使用正负号作为标记 */
var findDuplicates = function () {
    const n = nums.length
    const ans = []
    for (let i = 0; i < n; i++) {
        const x = Math.abs(nums[i])
        if (nums[x - 1] > 0) {
            nums[x - 1] = -nums[x - 1]
        } else {
            ans.push(x)
        }
    }
    return ans
}
findDuplicates([4, 3, 2, 7, 8, 2, 3, 1])